package com.treeroot.linkedlist;

/**
 * 创建一个环形的单向链表
 */
public class CircleSingleLinkedListByGPT {
    /**
     * 头节点，不存储数据
     */
    private Boy head = new Boy();

    /**
     * 遍历当前环形链表
     */
    public void list() {
        if (head.getNext() == null) {
            // 空链表
            System.out.println("链表为空");
            return;
        }

        Boy current = head.getNext();
        while (current != head) {
            System.out.println("小孩的编号为：" + current.getNo());
            current = current.getNext();
        }
    }

    /**
     * 根据用户输入计算出圈的顺序
     *
     * @param startNo  从第几个小孩开始数数
     * @param countNum 数几下
     * @param nums     最初有多少小孩在圈中
     */
    public void countOff(int startNo, int countNum, int nums) {
        // 参数校验
        if (startNo < 1 || startNo > nums) {
            System.out.println("参数输入有误，请重新输入");
            return;
        }

        // 构建循环链表
        createCircleLinkedList(nums);

        // 找到起始节点和结束节点
        Boy start = head;
        Boy end = head;
        for (int i = 0; i < startNo - 1; i++) {
            start = start.getNext();
        }
        while (end.getNext() != head) {
            end = end.getNext();
        }

        // 从起始节点开始数数，直到环中只剩下一个节点
        while (start != end) {
            // 找到报数为 countNum 的小孩
            for (int i = 0; i < countNum - 1; i++) {
                start = start.getNext();
                end = end.getNext();
            }

            // 删除该节点
            System.out.println("小孩" + start.getNo() + "出圈");
            start = start.getNext();
            end.setNext(start);
        }

        System.out.println("最后留在圈中的小孩编号为：" + start.getNo());
    }

    /**
     * 创建循环链表
     */
    private void createCircleLinkedList(int nums) {
        if (nums < 1) {
            System.out.println("smaller than 1");
            return;
        }

        Boy current = null;

        for (int i = 1; i <= nums; i++) {
            Boy boy = new Boy(i);
            if (i == 1) {
                head.setNext(boy);
            } else {
                current.setNext(boy);
            }
            boy.setNext(head);
            current = boy;
        }
    }

    public static void main(String[] args) {
        CircleSingleLinkedListByGPT circleSingleLinkedList = new CircleSingleLinkedListByGPT();
        circleSingleLinkedList.countOff(1, 2, 5);
    }
}
